/*
 *  src/algorithms/quick_sort.c
 *
 *  Harry Wei <harryxiyou@gmail.com> (C) 2011
 */
#include <glib.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

static int partition(int *num, int start, int end)
{
	int i = start;
	int j = end + 1;
	int x = num[start];
	int tmp = 0;

	while (1) {
		while (num[++i] < x && i < end);
		/* this is why 'j = end + 1' */
		while (num[--j] > x);
		if (i >= j) {
			break;
		}
		int tmp = num[i];
		num[i] = num[j];
		num[j] = tmp;
	}
	g_message("%s -- debug log start ........", __func__);
	for (tmp = 0; tmp < 10; tmp++) {
		g_print("%d ", num[tmp]);
	}
	g_print("\n");
	g_message("%s -- debug log over ........", __func__);
	num[start] = num[j];
	num[j] = x;
	return j;
}

void quick_sort(int *num, int start, int end)
{
	if (start < end) {
		int d_index = partition(num, start, end);
		g_message("index is %d", d_index);
		g_message("%s -- partition is %d", __func__, num[d_index]);
		quick_sort(num, start, d_index - 1);
		quick_sort(num, d_index + 1, end);
	}
}
